package com.brett.frame.learn.sort;
/**
 * 桶排序
 * @author lenovo
 *
 */

import com.brett.frame.learn.sort.choose.HeapChooseSort;
import com.brett.frame.learn.util.Tools;

public class BucketSort {
	HeapChooseSort heap = new HeapChooseSort();

	public int[] sort(int[] arr) {
		int max = this.max(arr);
		int[] bucket = new int[max];
		Tools.initZero(bucket);
		for (int i = 0; i < arr.length; i++) {
			bucket[arr[i]-1]++;
		}
		for (int i = 0, j = 0; i < max; i++) {
			if (bucket[i] > 0) {
				arr[j++] = i+1;
				bucket[i]--;
			}
		}
		return arr;
	}



	public int max(int[] arr) {
		heap.builderMaxHeap(arr);
		return arr[0];
	}
}
